from primes import prime, nrDistinctFactors, erastothenes

def solution1():
    n = 1
    sequenceLength = 0
    while True:
        if 4 == nrDistinctFactors(n):
            sequenceLength += 1
            print n, sequenceLength
            if (4 == sequenceLength):
                print n - 3
                break
        else:
            sequenceLength = 0
            
        n += 1

def solution2():
    limit = 500000
    sieve = limit * [0]
    primeGen = prime()
    
    for p in primeGen:
        if p >= limit: break

        i = p
        while i < limit:
            sieve[i] += 1
            i += p
    
    seqLength = 0
    
    for i in xrange(0, limit):
        if (4 == sieve[i]):
            seqLength += 1
            if (4 == seqLength):
                print i - 3
        else:
            seqLength = 0
            
def solution3():
    limit = 200000
    nrDistinctFactors = limit * [0]
    primes = erastothenes(limit)
    
    print "starting"

    n = 2
    sequenceLength = 0
    while True:
        for p in primes:
            if 0 != n % p: continue
            
            reduced = n            
            while True:
                reduced /= p
                if 0 != reduced % p: break
                
            nrDistinctFactors[n] = 1 + nrDistinctFactors[reduced]
            
            if 4 == nrDistinctFactors[n]:
                sequenceLength += 1
                if 4 == sequenceLength:
                    print n - 3
            else:
                sequenceLength = 0
            
            break
        
        n += 1
                    
solution3()